edu.claflin.finder.logic

Class BronKerboschHandler

java.lang.Object

edu.claflin.finder.logic.BronKerboschHandler

public class BronKerboschHandler
extends java.lang.Object

Code for finding maximal clique of a graph using the Bron-Kerbosch algorithm. https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm This was originally meant to be used for maximum complete bipartite graphs but I didn't figure out how to do that yet Somewhat of a WIP.

Constructor Summary

Constructors

Constructor and Description
BronKerboschHandler()

Method Summary

Modifier and Type	Method and Description
static void	bronKerbosch(java.util.ArrayList<Graph> results, Graph r, Graph p, Graph x) Recursive helper method to do the above.
static java.util.ArrayList<Graph>	bronKerbosch(Graph graph) Given a graph, finds all complete subgraphs.
static java.util.ArrayList<Graph>	bronKerboschBipartite(Graph graph) Bipartite Bron Kerbosch algorithm that usees the above to find all complete bipartite graphs within a bipartite graph.
static Graph	maximumCompleteClique(Graph graph) Given a graph, finds all complete subgraphs, and then returns the largest one.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BronKerboschHandler

public BronKerboschHandler()

Method Detail

maximumCompleteClique

public static Graph maximumCompleteClique(Graph graph)

Given a graph, finds all complete subgraphs, and then returns the largest one.

Parameters:

graph - the graph

Returns:

the largest complete subgraph (clique)

bronKerbosch

public static java.util.ArrayList<Graph> bronKerbosch(Graph graph)

Given a graph, finds all complete subgraphs.

Parameters:

graph - the graph

Returns:

an ArrayList of complete subgraphs, unordered

bronKerbosch

public static void bronKerbosch(java.util.ArrayList<Graph> results,
                                Graph r,
                                Graph p,
                                Graph x)

Recursive helper method to do the above.

Parameters:

results - result list. Passed between recursive calls to create output

r - graph r in wikipedia link

p - graph p in wikipedia link

x - graph x in wikipedia link

bronKerboschBipartite

public static java.util.ArrayList<Graph> bronKerboschBipartite(Graph graph)

Bipartite Bron Kerbosch algorithm that usees the above to find all complete bipartite graphs within a bipartite graph. This is done by adding edges between every node in both groups, using the above algorithm, and removing all the added edges later on. THIS ONLY WORKS ON GRAPHS THAT ARE BIPARTITE!

Parameters:

graph - the bipartite graph

Returns:

array list of bipartite graphs